struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
#include <vector>
using std::vector;


//使用一个中序遍历数组和后序遍历数组构造一棵树
//从后序数组找到根节点，然后切割中序数组，再切割后序数组（还要将后序数组的根节点去掉）
//切割后有左右子序列，就分别为左右子树的中序后序遍历数组
//递归继续处理
TreeNode* traversal(vector<int>& inorder, vector<int>& postorder) {
    if (postorder.size() == 0)
        return nullptr;

    int rootValue = postorder[postorder.size() - 1];
    TreeNode* root = new TreeNode(rootValue);

    if (postorder.size() == 1)  //root是叶子结点
        return root;

    // 取得切割点
    int delimiterIndex;
    for (delimiterIndex = 0; delimiterIndex < inorder.size();
            delimiterIndex++) {
        if (inorder[delimiterIndex] == rootValue)
            break;
    }



    // 切割中序数组
    vector<int> leftinorder(inorder.begin(),
                            inorder.begin() + delimiterIndex);
    vector<int> rightinorder(inorder.begin() + delimiterIndex + 1,
                            inorder.end());

    //后序数组删除最后一个元素
    postorder.resize(postorder.size() - 1);
    
    
    // 切割后序数组
    vector<int> leftpostorder(postorder.begin(),
                            postorder.begin() + leftinorder.size());
    vector<int> rightpostorder(postorder.begin() + leftinorder.size(),
                            postorder.end());

    //以root为根节点构造左右子树
    root->left = traversal(leftinorder, leftpostorder);
    root->right = traversal(rightinorder, rightpostorder);

    return root;
}


/*迭代器的用法：左开右闭
begin()+n表示从索引为n的元素开始，即第n-1个
切割标记点为d，则从0到索引d-1,故结束迭代器应该是索引d，（line35）
从索引d+1开始迭代，故开始迭代器是d+1（line36）


end()表示超尾，到end()的前一个结束
从begin()开始到end(),共遍历end()个元素，故（line45）要遍历leftinorder.size()个元素

总之，若用迭代器(nums.begin()+n,nums.begin()+m)遍历数组，则遍历索引从n到m-1的元素，共遍历m-n个元素
*/

TreeNode* buildTree_in_post(vector<int> inorder, vector<int> postorder) {
    if (postorder.size() == 0||inorder.size()==0)
        return nullptr;
    return traversal(inorder, postorder);
}





//用一个前序遍历数组和中序遍历数组构造一棵树
//和上面一样，只不过根节点在前序遍历的开头
TreeNode* traversal_(vector<int>& preorder,vector<int>& inorder)
{
    if(preorder.size()==0) return nullptr;

    int rootval=preorder[0];
    TreeNode* root=new TreeNode(rootval);

    //寻找切割点
    int delimiterIndex;
    for(delimiterIndex=0;delimiterIndex<inorder.size();delimiterIndex++)
    {
        if(inorder[delimiterIndex]==rootval) break;
    }

    //切割中序数组
    vector<int> leftInorder(inorder.begin(),inorder.begin()+delimiterIndex);
    vector<int> rightInorder(inorder.begin()+delimiterIndex+1,
                            inorder.end());

    //切割前序数组
    preorder.erase(preorder.begin());
    vector<int> leftPreorder(preorder.begin(),
                            preorder.begin()+leftInorder.size());
    vector<int> rightPreorder(preorder.begin()+leftInorder.size(),      //跳过leftorder.size()个元素
                            preorder.end());

    root->left=traversal_(leftPreorder,leftInorder);
    root->right=traversal_(rightPreorder,rightInorder);

    return root;   
}

TreeNode* buildTree_pre_in(vector<int> preorder,vector<int> inorder)
{
    if(preorder.size()==0) return nullptr;
    return traversal_(preorder,inorder);
}